package com.yoshino.leetcode.interview150.graph;

import java.util.*;

class Solution {
    public int numIslands(char[][] grid) {
        // 找到一块，就将所有陆地感染成1
        int m = grid.length, n = grid[0].length, res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    infect(grid, i, j);
                    res++;
                }
            }
        }
        return res;
    }

    private void infect(char[][] grid, int i, int j) {
        if (j < 0 || j >= grid[0].length || i < 0 || i >= grid.length || grid[i][j] != '1') {
            return;
        }
        grid[i][j] = '2';
        infect(grid, i - 1, j);
        infect(grid, i + 1, j);
        infect(grid, i, j - 1);
        infect(grid, i, j + 1);
    }

    public void solve(char[][] board) {
        // 借鉴上一题，将边缘的置为1
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                dfs(board, i, n - 1);
            }
        }
        for (int i = 1; i < n - 1; i++) {
            if (board[0][i] == 'O') {
                dfs(board, 0, i);
            }
            if (board[m - 1][i] == 'O') {
                dfs(board, m - 1, i);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '1') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    private void dfs(char[][] board, int i, int j) {
        if (j < 0 || j >= board[0].length || i < 0 || i >= board.length || board[i][j] != 'O') {
            return;
        }
        board[i][j] = '1';
        dfs(board, i + 1, j);
        dfs(board, i - 1, j);
        dfs(board, i, j - 1);
        dfs(board, i, j + 1);
    }

    public Node cloneGraph(Node node) {
        // 广度遍历
        if (node == null) {
            return node;
        }
        // 保存已经复制的节点
        Map<Node, Node> map = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        map.put(node, new Node(node.val, new ArrayList<>()));
        queue.add(node);
        while (!queue.isEmpty()) {
            Node cur = queue.remove();
            // 遍历该点的邻居
            for (Node neighbor : cur.neighbors) {
                if (!map.containsKey(neighbor)) {
                    // 没创建过
                    map.put(neighbor, new Node(neighbor.val, new ArrayList<>()));
                    queue.add(neighbor);
                }
                // 更新当前节点的邻居，克隆体
                map.get(cur).neighbors.add(map.get(neighbor));
            }
        }
        return map.get(node);
    }

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int nvars = 0;
        Map<String, Integer> variables  = new HashMap<>();
        int n = equations.size();
        for (int i = 0; i < n; i++) {
            if (!variables.containsKey(equations.get(i).get(0))) {
                variables.put(equations.get(i).get(0), nvars++);
            }
            if (!variables.containsKey(equations.get(i).get(1))) {
                variables.put(equations.get(i).get(1), nvars++);
            }
        }
        double[][] graph = new double[nvars][nvars];
        for (int i = 0; i < nvars; i++) {
            Arrays.fill(graph[i], -1.0);
        }
        for (int i = 0; i < n; i++) {
            int va = variables.get(equations.get(i).get(0)), vb = variables.get(equations.get(i).get(1));
            graph[va][vb] = values[i];
            graph[vb][va] = 1.0 / values[i];
        }
        for (int k = 0; k < nvars; k++) {
            for (int i = 0; i < nvars; i++) {
                for (int j = 0; j < nvars; j++) {
                    if (graph[i][k] > 0 && graph[k][j] > 0) {
                        graph[i][j] = graph[i][k] * graph[k][j];
                    }
                }
            }
        }
        int count = queries.size();
        double[] res = new double[count];
        for (int i = 0; i < count; i++) {
            List<String> query = queries.get(i);
            double result = -1.0;
            if (variables.containsKey(query.get(0)) && variables.containsKey(query.get(1))) {
                int ia = variables.get(query.get(0)), ib = variables.get(query.get(1));
                if (graph[ia][ib] > 0) {
                    result = graph[ia][ib];
                }
            }
            res[i] = result;
        }
        return res;
    }

    List<List<Integer>> list = new ArrayList<>();
    int visit[];
    boolean isvaild = true;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        visit = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            list.add(new ArrayList<>());
        }
        for (int[] info : prerequisites) {
            //学info[0]之前要先学info[1],所以info[1]指向info[0],
            //所以在info[1]的ArrayList中存储它指向哪个科目
            list.get(info[1]).add(info[0]);
        }
        for (int i = 0; i < numCourses; i++) {
            if (visit[i] == 0) {
                dfs(i);
            }
        }
        return isvaild;
    }

    public void dfs(int v){
        visit[v] = 1;
        //遍历该科目指向的学科
        for (int w : list.get(v)) {
            //如果指向的某一学科未搜索过，则深搜
            if (visit[w] == 0) {
                dfs(w);
                if (!isvaild) {
                    return;
                }
            } else if (visit[w] == 1) {
                //如果指向的某一学科在搜索中，则有环，标记isVaild
                isvaild = false;
                return;
            }
        }
        //因为该科目已经完成深搜，所以标记它的状态为搜索过
        visit[v] = 2;
    }

    // 前置完成的课
    List<List<Integer>> preFinish = new ArrayList<>();
    // 每个课的状态
    int[] isFin;
    // 是否有效
    boolean vaild = true;
    // 结果
    List<Integer> res;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        isFin = new int[numCourses];
        res = new ArrayList<>(numCourses);
        for (int i = 0; i < numCourses; i++) {
            preFinish.add(new ArrayList<>());
        }
        for (int[] pre : prerequisites) {
            preFinish.get(pre[0]).add(pre[1]);
        }
        for (int i = 0; i < numCourses; i++) {
            if (isFin[i] == 0) {
                dfs2(i);
            }
        }
        if (vaild) {
            // 有效
            return res.stream().mapToInt(Integer::intValue).toArray();
        }
        return new int[0];
    }

    private void dfs2(int v) {
        // 正在遍历中
        isFin[v] = 1;
        for (int w : preFinish.get(v)) {
            // 需要完成的课程
            if (isFin[w] == 0) {
                dfs2(w);
                if (!vaild) {
                    return;
                }
            } else if (isFin[w] == 1) {
                // 有循环
                vaild = false;
                return;
            }
        }
        // 遍历完成，该课可以先上
        isFin[v] = 2;
        res.add(v);
    }
}